Một số phần của Đông Malaysia ngày nay, đặc biệt là các vùng ven biển đã từng là bộ phận của Vương quốc Hồi giáo Brunei[9]. Tuy nhiên, hầu hết những khu vực trong nội địa là các bộ tộc độc lập. Vào giữa thế kỷ XVII, phần phía bắc và đông của vùng ven biển của Sabah được nhượng lại cho Vương quốc Hồi giáo Sulu trong khi phần lớn Sarawak vẫn là thuộc về Brunei. Bắt đầu từ giữa thế kỷ XIX, cả Sarawak và Sabah đều trở thành nơi bảo hộ của Anh Quốc và năm 1946 cả hai trở thành những thuộc địa riêng biệt của Anh.